package x.y.z;

public class LeetCode_0109 {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head);
    }

    private TreeNode buildTree(ListNode node) {
        if (node == null) {
            return null;
        }
        if (node.next == null) {
            return new TreeNode(node.val);
        }
        ListNode prev = null;
        ListNode slow = node;
        ListNode fast = node;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = buildTree(node);
        root.right = buildTree(slow.next);
        return root;
    }
}
